Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Автомати з магазинною пам’яттю. Контекстно-вільні граматики

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики

Інформація про роботу

Рік:
2006
Тип роботи:
Курсова робота
Предмет:
Дискретна математика
Група:
ПМ-31

Частина тексту файла

Міністерство освіти і науки України Національний університет “Львівська політехніка” кафедра прикладної математики КУРСОВА РОБОТА з курсу дискретна математика на тему: „Автомати з магазинною пам’яттю. Контекстно-вільні граматики” ЗМІСТ Вступ. Основні поняття теорії формальних мов і граматик............................................................................................................3 Означення МП-автомата……………………………………………………………….3 Варіанти МП-автоматів………………………………………………………………..6 Еквівалентність МП-автоматів і КВ-граматик……………………………………...10 Детерміновані МП-автомати…………………………………………………………16 Синтез МП-автомата………………………………….................................................21 Програмна реалізація синтезу ДМП-автомата……………………………………...23 Список використаної літератури…………………….................................................27 Основні поняття теорії формальних мов і граматик. Для того, щоб зрозуміти теорію алгоритмічних мов, необхідно оперувати найпростішими, але найфундаментальнішими поняттями теорії формальних мов і граматик, мати чітку уяву про ієрархію мови – літера, слово, мова. Отже, літера – це простий неподільний знак. Множина літер утворює алфавіт. Ланцюжок (слово, стрічка) – це впорядкована скінченна послідовність літер алфавіту. ε–порожній ланцюжок, ланцюжок нульової довжини. Над ланцюжками допускаються операції конкатенації (об’єднання ланцюжків) та обертання стрічок. Мовою LA, породженою алфавітом А, називається сукупність всіх стрічок, отриманих у даній мові. Дамо також означення граматики. Формальною породжуючою граматикою G називається четвірка <N,Т,Р,S> , де Т – скінченна не порожня множина символів, яка називається термінальним або основним словником граматики G; N – скінченна не порожня множина символів, що називається нетермінальним (допоміжним) словником граматики G, причому ТN=Ø, Т N=V –об’єднаний словник граматики G; S – початковий символ або аксіома граматики G, S – нетермінал і є головною метою граматики G; Р – скінченна множина правил граматики G, елемент цієї множини можна задати у вигляді пари (α , β); ця пара – правило виводу або правило підстановки і часто записується у вигляді α→β. Варто зауважити, що α,β{NТ}* (A*– множина всіх можливих ланцюжків над алфавітом А, A*=А0А1А2...Аn... і називається замиканням алфавіту А або повною ітерацією; є ще неповна ітерація:А+ = A* \{ε}). Правила підстановки називають також схемою граматики. Означимо відношення G (відношення в граматиці G, надалі писатимемо без позначки внизу, коли розумітимемо про яку граматику йдеться) на множині (NT)* так: якщо αβγ – стрічка з (NT)* і β → δ – правило з Р, то αβγ  αδγ. Транзитивне замикання відношення  позначають через+ (φ + ψ читається: ψ виводима з φ нетривіальним чином), а його рефлексивне і транзитивне замикання: * (φ * ψ читається: ψ виводима з φ). Існує чотири класи мов і граматик за Хомським, але ми користуватимемося класом, що містить так звані контексно-вільні мови (КВ-мови). Це – мови, що породжуються граматиками, які мають правила виводу такого виду: α→β, де αN, βV+, тобто ліві частини правил виводу мають лише один нетермінальний символ. Означення МП-автомата Автомат з магазинною пам’яттю—розпізнавач, який представляє собою звичайну модель синтаксичних аналізаторів контекстно-вільних мов. Автомат з магазинною пам’яттю—односторонній недетермінований розпізнавач , в потенційно нескінченній пам’яті якого елементи інформації зберігаються і використовуються так само, як патрони в магазині автоматичної зброї, тобто в кожний момент доступний тільки верхній елемент магазина. Розпізнавач такого типу зображений на рисунку 1. А1 А2  Аn  Вхідна стрічка (тільки читати) Z1  Z2    Zm   Магазин Рис.1.Автомат з магазинною пам’ят...
Антиботан аватар за замовчуванням

01.01.1970 03:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини